class Solution:
    def findIntegers(self, num: int) -> int:
        dp = [0] * 31
        dp[0] = dp[1] = 1
        for i in range(2, 31):
            dp[i] = dp[i - 1] + dp[i - 2]

        pre = 0
        res = 0

        for i in range(29, -1, -1):
            val = (1 << i)
            if num & val:
                num -= val
                res += dp[i + 1]
                if pre == 1:
                    break
                pre = 1
            else:
                pre = 0

            if i == 0:
                res += 1

        return res


if __name__ == "__main__":
    print(Solution().findIntegers(5))  # 5

    # 自制用例
    print(Solution().findIntegers(3))  # 3
    print(Solution().findIntegers(4))  # 4
    print(Solution().findIntegers(8))  # 6
    print(Solution().findIntegers(16))  # 9
